//https://leetcode.cn/problems/average-of-levels-in-binary-tree/
package codeRandomThoughts.Test637二叉树的层平均值;

import codeRandomThoughts.utils.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //层序遍历用队列实现
        Queue<TreeNode> queue = new LinkedList<>();
        List<Double> results = new ArrayList<>();
        double sum = 0;
        if (root == null)
            return results;

        //记录每层节点个数
        int npl = 0; //number per level
        TreeNode node = root;
        queue.offer(node);
        while (!queue.isEmpty()) {
            npl = queue.size();
            int i=npl;
            while (npl > 0) {
                node = queue.poll();
                sum+=node.val;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                npl--;
            }
            results.add(sum/i);
            sum=0;
        }
        return results;

    }
}
